Nedelin gia nhập Hồng quân năm 1920, ở tuổi 18, và chiến đấu như một tình nguyện viên trong Nội chiến Nga cho đến khi kết thúc vào năm 1923. Năm sau, ông gia nhập Đảng Cộng sản Liên Xô, và được nhập ngũ trở lại Hồng quân, trở thành chỉ huy pháo binh.[1] Từ năm 1937 đến năm 1939, Nedelin chiến đấu trong Nội chiến Tây Ban Nha với tư cách là tình nguyện viên nước ngoài cho Chính phủ Cộng hòa, và cùng năm đó được bổ nhiệm làm chỉ huy Trung đoàn Pháo binh số 13 trong Hồng quân Liên Xô.[2] Năm 1940, ông được bổ nhiệm chỉ huy pháo binh của Sư đoàn súng trường 160 sau khi trở về từ Tây Ban Nha, và tham gia Chiến tranh Mùa đông cho đến năm 1940.

Năm 1941, khi Chiến tranh Vệ quốc Vĩ đại nổ ra, Nedelin được bổ nhiệm làm chỉ huy đầu tiên của Lữ đoàn chống tăng 4, sau đó là chỉ huy pháo binh của Tập đoàn quân 18, và sau đó là pháo binh của Tập đoàn quân 37, nơi ông ở lại cho đến năm 1943, trước khi được chuyển sang chỉ huy pháo binh của Tập đoàn quân 56.[2] Năm 1943, ông được bổ nhiệm làm Phó tư lệnh pháo binh Phương diện quân Bắc Kavkaz.[1] Từ đây Nedelin chuyển sang chỉ huy Quân đoàn pháo binh V, rồi pháo binh của mặt trận tây nam, rồi pháo binh của Phương diện quân Ukraina 3, nơi ông ở lại từ năm 1943 đến năm 1945, đóng một vai trò đặc biệt quan trọng trong việc đánh chiếm Hungary. Năm 1945, Nedelin trở thành trợ lý chỉ huy và sau đó là sĩ quan chỉ huy pháo binh của Cụm binh đoàn Phương Nam Liên Xô.

Năm 1946, sau khi Thế chiến thứ hai kết thúc, Nedelin trở thành tham mưu trưởng Tổng cục pháo binh Quân đội Liên Xô, rồi tham mưu trưởng pháo binh, rồi Phó tổng tư lệnh pháo binh. Năm 1948, ông trở thành Cục trưởng Cục pháo binh Quân đội Liên Xô trước khi trở thành Tổng tư lệnh pháo binh từ năm 1950 đến năm 1952, và sau một thời gian ngắn giữ chức Thứ trưởng Bộ Quân sự, ông trở lại làm Tổng tư lệnh pháo binh từ năm 1953 đến năm 1955.[1][2] Từ năm 1955, ông là Thứ trưởng Bộ Quốc phòng, từ 1959 kiêm nhiệm Tổng tư lệnh Lực lượng Tên lửa Chiến lược.